package com.kuang.array;

    /*给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。
    请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

        示例 1：
        输入：nums = [4,3,2,7,8,2,3,1]
        输出：[5,6]                            */


import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * @author kjx
 */
public class FindTheLost {

    //开局先来一个无脑的 HaspMap
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> result = new ArrayList<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        int n = nums.length;
        //将数组下标数值反着存入map
        for (int i = 0; i < n; i++) {
            map.put(nums[i], i);
        }
        //遍历1-n数字
        for (int i = 1; i <= n; i++) {
            if (map.get(i) == null) {
                result.add(i);
            }
        }
        return result;
    }


    //突然根据那个布隆过滤想到了另外一种，制作一个标记数组
    public List<Integer> findDisappearedNumbers2(int[] nums) {
        int n = nums.length;
        List<Integer> result = new ArrayList<>();
        int[] flag = new int[n + 1];
        Arrays.fill(flag, 0);
        //根据原数组标记flag[]
        for (int num : nums) {
            flag[num]++;
        }
        //还是0的下标就是没出现的数字
        for (int i = 1; i <= n; i++) {
            if (flag[i] == 0) {
                result.add(i);
            }
        }
        return result;
    }


    //试试不用辅助空间,其实我们忽略了一个很巧妙的关系，就是数组里面的数字大小减去1的范围就是所有下标的范围；
    //因此我们可以利用这一点对原数组进行一些操作标记,这里变成负数，因为我们需要他的正数来知道原来的数据
    public static List<Integer> findDisappearedNumbers3(int[] nums) {
        int n = nums.length;
        List<Integer> result = new ArrayList<>();
        //第一次遍历
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            //把负数num复原
            if (num < 0) {
                num = -num;
            }
            //如果已经是负数不需要取反
            if (nums[num - 1] > 0) {
                nums[num - 1] = -nums[num - 1];
            }
        }
        //原来数组没有变化，也就是还大于0的对应的下标就是缺少的
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                result.add(i + 1);
            }
        }
        return result;
    }


    public static void main(String[] args) {
        int[] test = {4, 3, 2, 7, 8, 2, 3, 1};
        System.out.println(findDisappearedNumbers3(test));
    }
}
